package algorithm.search;

import com.alibaba.fastjson.JSON;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 二分查找（折半查找）
 *
 * @author LiDong
 * @version 1.0.0
 * @createTime 2021年11月01日 21:37:00
 */
public class BinarySearch {

    private static final Logger logger = LoggerFactory.getLogger(BinarySearch.class);

    /**
     * 二分查找
     */
    int[] arr = {10, 7, 4, 2, 6, 9, 8, 3, 22, 3, 44, 5};


    @Test
    public void test() {
        int num = 5;
        logger.info("数字:{} 在第：{} 位", num, sortFindNum(num, arr));
    }

    private int sortFindNum(int num, int[] arr) {
        // 先对数组排序
        for (int j = 0; j < arr.length - 1; j++) {
            for (int k = 0; k < arr.length - 1; k++) {
                if (arr[k] > arr[k + 1]) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
            }
        }
        System.out.println("排序后的数组为：" + JSON.toJSONString(arr));
        // 对有序数组 二分查找
        int numOne = findNumOne(num, 0, arr.length - 1);
        return findNumTwo(num, 0, arr.length - 1);
    }


    /**
     * 方法一 ： 缩小 start end 的值当 end-start==1的时候 num 和 arr[start] arr[end] 进行比较
     *
     * @param num
     * @param start
     * @param end
     * @return
     */
    private int findNumOne(int num, int start, int end) {
        while (start < end) {
            if (end - start == 1) {
                break;
            }
            int flag = (start + end) / 2;
            int mid = arr[flag];
            logger.info("中间 mid:{}", flag);
            if (num == mid) {
                return flag;
            } else if (num > mid) {
                start = flag;
            } else {
                end = flag;
            }
        }
        return 0;
    }

    /**
     * 递归方式
     *
     * @param num
     * @param start
     * @param end
     * @return
     */
    private int findNumTwo(int num, int start, int end) {
        if (start > end) return 0;
        int flag = (start + end) / 2;
        logger.info("===>" + flag);
        if (num == arr[flag]) {
            return flag;
        } else if (num > arr[flag]) {
            start = flag;
        } else if (num < arr[flag]) {
            end = flag;
        }
        return findNumTwo(num, start, end);
    }


}
